TJOI2015旅游

发表于
字数统计: 1,632字 | 阅读时长 ≈ 9min

[TJOI2015]旅游

问题描述

为了提高智商，ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可以互达。每座城市都有一种宝石，有一定的价格。ZJY为了赚取最高利益，她会选择从A城市买入再转手卖到B城市。由于ZJY买宝石时经常卖萌，因而凡是ZJY路过的城市，这座城市的宝石价格会上涨。让我们来算算ZJY旅游完之后能够赚取的最大利润。（如a城市宝石价格为v，则ZJY出售价格也为v）

输入格式

第一行输入一个正整数N，表示城市个数。

接下来一行输入N个正整数表示每座城市宝石的最初价格p，每个宝石的初始价格不超过100。

第三行开始连续输入N-1行，每行有两个数字x和y。表示x城市和y城市有一条路径。城市编号从1开始。

下一行输入一个整数Q，表示询问次数。

接下来Q行，每行输入三个正整数a,b,v，表示ZJY从a旅游到b，城市宝石上涨v。
即是询问a—>b(有方向)间路径上的max(Price[j]−Price[i])) 且j到a的距离比i到a大 。然后把这条路径上所有点的点权+v。

输出格式

对于每次询问，输出ZJY可能获得的最大利润，如果亏本则输出0。

数据范围

1≤ N≤50000， 1≤Q ≤50000

首先考虑一条链的情况怎么做。

区间整体加，这提示我们可以用线段树维护。容易想到维护区间最大值、区间最小值、$max($右边-左边$)$、$max($左边-右边$)$。$max($右边-左边$)$的值由左儿子的$max($右边-左边$)$、右儿子的$max($右边-左边$)$、右儿子最大值-左儿子最小值共同决定。$max($左边-右边$)$同理。

询问一段区间，只需要把线段树上对应区间取出来按照上述规则合并，判断方向之后决定取$max($右边-左边$)$还是$max($左边-右边$)$即可。

问题扩展到树上时，显然使用树链剖分，线段树维护相同的值，只不过要把路径拆成$u->LCA$、$LCA->v$两段分别处理，注意方向。

把线段树节点开成结构体形式或许方便实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 100005
#define MAXM 200005
#define MAXT 800005
using namespace std;

char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int sign=0,v=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')sign=1,s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

int N,Q,A[MAXN];
int en[MAXM],nex[MAXM],las[MAXN],tot;
int fa[MAXN],hson[MAXN],sz[MAXN],id[MAXN],idd[MAXN],dep[MAXN],anc[MAXN],lab;
struct node{
	int minv,maxv,ans[2];
	void init(){minv=1e9;maxv=ans[0]=ans[1]=-1e9;}
	void add(int v){minv+=v;maxv+=v;}
};

int tmax(int a,int b,int c){
	if(a>=b&&a>=c)return a;
	if(b>=c)return b;
	return c;
}

void Add(int x,int y){
	en[++tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
}

namespace Seg{
	int ls[MAXT],rs[MAXT],lazy[MAXT],tot;
	node mt[MAXT];

	node Update(node l,node r){
		node ret;ret.init();
		ret.maxv=max(l.maxv,r.maxv);
		ret.minv=min(l.minv,r.minv);
		ret.ans[0]=tmax(l.ans[0],r.ans[0],l.maxv-r.minv);
		ret.ans[1]=tmax(l.ans[1],r.ans[1],r.maxv-l.minv);
		return ret;
	}

	void Putdown(int p){
		lazy[ls[p]]+=lazy[p];
		lazy[rs[p]]+=lazy[p];
		mt[ls[p]].add(lazy[p]);
		mt[rs[p]].add(lazy[p]);
		lazy[p]=0;
	}

	int Build(int l,int r){
		int p=++tot,mid=l+r>>1;
		if(l==r){
			mt[p].init();
			mt[p].maxv=mt[p].minv=A[idd[l]];
			return p;
		}
		ls[p]=Build(l,mid);
		rs[p]=Build(mid+1,r);
		mt[p]=Update(mt[ls[p]],mt[rs[p]]);
		return p;
	}

	void Modify(int p,int l,int r,int x,int y,int v){
		if(lazy[p])Putdown(p);
		if(x<=l&&r<=y){
			mt[p].add(v);
			lazy[p]+=v;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid)Modify(ls[p],l,mid,x,y,v);
		if(mid<y)Modify(rs[p],mid+1,r,x,y,v);
		mt[p]=Update(mt[ls[p]],mt[rs[p]]);
	}

	node GetSeg(int p,int l,int r,int x,int y){
		if(lazy[p])Putdown(p);
		if(x<=l&&r<=y)return mt[p];
		int mid=l+r>>1;
		node tmp;tmp.init();
		if(x<=mid)tmp=Update(GetSeg(ls[p],l,mid,x,y),tmp);
		if(mid<y)tmp=Update(tmp,GetSeg(rs[p],mid+1,r,x,y));
		return tmp;
	}
}

void GetSon(int x,int f){
	int i,y;
	sz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
	for(i=las[x];i;i=nex[i]){
		y=en[i];if(y==f)continue;
		GetSon(y,x);
		sz[x]+=sz[y];
		if(sz[y]>sz[hson[x]])hson[x]=y;
	}
}

void Connect(int x,int f,int aa){
	id[x]=++lab;anc[x]=aa;idd[lab]=x;
	int i,y;
	if(hson[x])Connect(hson[x],x,aa);
	for(i=las[x];i;i=nex[i]){
		y=en[i];if(y==f||y==hson[x])continue;
		Connect(y,x,y);
	}
}

void Init(){
	GetSon(1,0);
	Connect(1,0,1);
	Seg::Build(1,N);
}

int LCA(int x,int y){
	while(anc[x]!=anc[y]){
		if(dep[anc[x]]<dep[anc[y]])swap(x,y);
		x=fa[anc[x]];
	}
	return dep[x]<dep[y]?x:y;
}

int GetAns(int x,int y){
	int lca=LCA(x,y);
	node l,r,ans;l.init();r.init();
	while(anc[x]!=anc[lca]){
		l=Seg::Update(Seg::GetSeg(1,1,N,id[anc[x]],id[x]),l);
		x=fa[anc[x]];
	}
	l=Seg::Update(Seg::GetSeg(1,1,N,id[lca],id[x]),l);
	while(anc[y]!=anc[lca]){
		r=Seg::Update(Seg::GetSeg(1,1,N,id[anc[y]],id[y]),r);
		y=fa[anc[y]];
	}
	r=Seg::Update(Seg::GetSeg(1,1,N,id[lca],id[y]),r);
	swap(l.ans[0],l.ans[1]);//swap(r.ans[0],r.ans[1]);
	ans=Seg::Update(l,r);
	return max(0,ans.ans[1]);
}

void Modify(int x,int y,int v){
	while(anc[x]!=anc[y]){
		if(dep[anc[x]]<dep[anc[y]])swap(x,y);
		Seg::Modify(1,1,N,id[anc[x]],id[x],v);
		x=fa[anc[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	Seg::Modify(1,1,N,id[y],id[x],v);
}

int main(){
	int i,x,y,v;
	N=_R();
	for(i=1;i<=N;i++)A[i]=_R();
	for(i=1;i<N;i++){
		x=_R();y=_R();
		Add(x,y);Add(y,x);
	}
	Init();
	Q=_R();
	for(i=1;i<=Q;i++){
		x=_R();y=_R();v=_R();
		printf("%d\n",GetAns(x,y));
		Modify(x,y,v);
	}
}